# def INCREMENT(A):
#     i = 0
#     while i < A.length and A[i] == 1:
#         A[i] = 0
#         i += 1
#     if i < A.length:
#         A[i] = 1
#         if i > A.max:
#             A.max = i
#     else:
#         A.max = -1
#
#
# def RESET(A):
#     for i in range(A.max):
#         A[i] = 0
#     A.max = -1

import time


def main():
    print("请输入一共有多少个物品：", end=" ")
    n = int(input())
    value = []
    value.append(0)
    weight = []
    weight.append(0)
    print("请输入每个物品的价值：", end=" ")
    value_all = input().split(" ")
    for value_one in value_all:
        value.append(int(value_one))
    print("请输入每个物品的重量：", end=" ")
    weight_all = input().split(" ")
    for weight_one in weight_all:
        weight.append(int(weight_one))
    print("请输入背包重量：", end=" ")
    bag_weight = int(input())

    # time1 = float(time.clock())  # 保存程序开始时的时间
    max_value = [([0] * (bag_weight + 1)) for i in range(0, n + 1)]
    for i in range(1, n + 1):
        for j in range(1, bag_weight + 1):
            if (j >= weight[i]):
                max_value[i][j] = max(max_value[i - 1][j], max_value[i - 1][j - weight[i]] + value[i])
            else:
                max_value[i][j] = max_value[i - 1][j]
    print("当背包重量为%d时，能拿物品的最大价值为：%d" % (bag_weight, max_value[n][bag_weight]))
    item = [0 for i in range(n + 2)]
    m = n
    while m >= 1:
        i = m
        if (max_value[i][bag_weight] == max_value[i - 1][bag_weight]):
            item[i] = 0
        else:
            item[i] = 1
            bag_weight -= weight[i]
        m -= 1
    print("所能拿的物品为(1为拿，0为不拿）：", end=" ")
    for i in range(1, n + 1):
        print(item[i], end=" ")
    # time2 = float(time.clock())
    # print("\n程序运行时间：%f" % (time2 - time1))


if __name__ == '__main__':
    main()
